package com.hdu.hot100.list;

import java.util.List;

public class lc148 {


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        public ListNode sortList(ListNode head)
        {
             if (head == null || head.next == null) return head;

             ListNode half = getHalf(head);
             ListNode next = half.next;
             half.next = null;

             return merge(sortList(head), sortList(next));
        }


        ListNode getHalf(ListNode head)
        {
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null)
            {
                fast = fast.next.next;
                if (fast == null) return slow;
                slow = slow.next;
            }
            return slow;
        }

        ListNode merge(ListNode p, ListNode q)
        {
            ListNode dummy = new ListNode(0);
            ListNode cur = dummy;
            while (p != null && q != null)
            {
                if (p.val < q.val)
                {
                    cur.next = p;
                    p = p.next;
                }
                else
                {
                    cur.next = q;
                    q = q.next;
                }
                cur = cur.next;
            }
            if (p != null) cur.next = p;
            if (q != null) cur.next = q;
            return dummy.next;
        }
    }
}
